Збирови префикса и разлике суседних елемената низа
Ако је дат низ елемената збир свих елемената у интервалу позиција \([a, b]\) се може израчунати као разлика између збира свих елемената у интервалу позиција \([0, b]\) и збира елемената у интервалу позиција \([0, a-1]\).
На пример, размотримо како да израчунамо збир елемената на позицијама из интервала [3, 5] (тј. на позицијама 3, 4 и 5) у низу 4, 2, 3, 1, 5, 6, 9, 2. На тим позицијама се налазе елементи 1, 5 и 6 и збир им је \(1+5+6 = 12\). Збир свих елемената из интевала позиција \([0, 5]\) је \(4+2+3+1+5+6 = 21\), док је збир свих елемената из интервала позиција \([0, 2]\) једнак \(4 + 2 + 3 = 9\). Разлика \(21-9\) управо је једнака 12.
Ова наизглед веома једноставна особина сабирања може значајно помоћи убрзању разних алгоритама у којима су нам потребни збирови узастопних елемената низа. Наиме, ако знамо збирове свих префикса низа тј. збирове на свим интервалима \([0, k)\), за \(k=0\) до \(n\) (а њих можемо израчунати током фазе претпроцесирања, инкрементално, у линеарној сложености), тада у константној сложености (једним одузимањем) можемо израчунати збир произвољног сегмента низа.
У језику C++ парцијалне збирове је могуће израчунати и коришћењем
библиотечке функције partial_sum, која, наравно, ради у
линеарној сложености. Функцији се прослеђују два итератора на део низа
који се сабира, као и итератор на почетак низа у који се смештају
резултати (пошто се унапред зна колико ће елемената бити, тај низ се
унапред алоцира).
Дакле, од датог низа, низ збирова префикса можемо израчунати у линеарној сложености, али важи и обратно. Од низа префикса, у линеарној сложености можемо израчунати елементе оригиналног низа. Важи чак и јаче тврђење од тога, јер сваки конкретни елемент низа можемо наћи у константној сложености, одузимањем два суседна збира префикса. Дакле, прелазак са низа на збирове његових префикса можемо сматрати променом репрезентације (нема смисла чувати и једно и друго истовремено у меморији).
Приметимо огромну сличност са интегралним и диференцијалним рачуном. Израчунавање збирова префикса одговара одређеном интеграљењу, разлика збирова префикса одговара Њутн-Лајбницовој формули, док израчунавање разлике суседних елемената одговара диференцирању. Интеграљење и диференцирање су међусобно инверзне операције.
Дуалан приступ збировима префикса је промена репрезентације у којој уместо низа чувамо разлике суседних елемената. Повратак на оргинални низ се онда може извршити у линеарној сложености тако што израчунамо збирове префикса низа разлика. Ова репрезентација нам омогућава да веома ефикасно мењамо сегменте низа тако што све елементе из неког задатог сегмента увећамо или умањимо за неку фиксну вредност.
Збирови префикса и разлике суседних елемената низа
Ако је дат низ елемената збир свих елемената у интервалу позиција \([a, b]\) се може израчунати као разлика између збира свих елемената у интервалу позиција \([0, b]\) и збира елемената у интервалу позиција \([0, a-1]\).
На пример, размотримо како да израчунамо збир елемената на позицијама из интервала [3, 5] (тј. на позицијама 3, 4 и 5) у низу 4, 2, 3, 1, 5, 6, 9, 2. На тим позицијама се налазе елементи 1, 5 и 6 и збир им је \(1+5+6 = 12\). Збир свих елемената из интевала позиција \([0, 5]\) је \(4+2+3+1+5+6 = 21\), док је збир свих елемената из интервала позиција \([0, 2]\) једнак \(4 + 2 + 3 = 9\). Разлика \(21-9\) управо је једнака 12.
Ова наизглед веома једноставна особина сабирања може значајно помоћи убрзању разних алгоритама у којима су нам потребни збирови узастопних елемената низа. Наиме, ако знамо збирове свих префикса низа тј. збирове на свим интервалима \([0, k)\), за \(k=0\) до \(n\) (а њих можемо израчунати током фазе претпроцесирања, инкрементално, у линеарној сложености), тада у константној сложености (једним одузимањем) можемо израчунати збир произвољног сегмента низа.
Дакле, од датог низа, низ збирова префикса можемо израчунати у линеарној сложености, али важи и обратно. Од низа префикса, у линеарној сложености можемо израчунати елементе оригиналног низа. Важи чак и јаче тврђење од тога, јер сваки конкретни елемент низа можемо наћи у константној сложености, одузимањем два суседна збира префикса. Дакле, прелазак са низа на збирове његових префикса можемо сматрати променом репрезентације (нема смисла чувати и једно и друго истовремено у меморији).
Приметимо огромну сличност са интегралним и диференцијалним рачуном. Израчунавање збирова префикса одговара одређеном интеграљењу, разлика збирова префикса одговара Њутн-Лајбницовој формули, док израчунавање разлике суседних елемената одговара диференцирању. Интеграљење и диференцирање су међусобно инверзне операције.
Дуалан приступ збировима префикса је промена репрезентације у којој уместо низа чувамо разлике суседних елемената. Повратак на оргинални низ се онда може извршити у линеарној сложености тако што израчунамо збирове префикса низа разлика. Ова репрезентација нам омогућава да веома ефикасно мењамо сегменте низа тако што све елементе из неког задатог сегмента увећамо или умањимо за неку фиксну вредност.